package com.zhouxianglh.p22;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    public static List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if (n == 0) {
            return list;
        }
        generateParenthesis(n, 0, 0, new StringBuilder(), list);
        return list;
    }

    public static void generateParenthesis(int level, int left, int right, StringBuilder str, List<String> list) {
        if (level == 0) {
            StringBuilder stringBuilder = new StringBuilder(str);
            for (int i = 0, j = left - right; i < j; i++) {
                stringBuilder.append(')');
            }
            list.add(stringBuilder.toString());
            return;
        }
        //
        StringBuilder stringBuilder = new StringBuilder(str);
        stringBuilder.append('(');
        left++;
        //无右括号情况
        generateParenthesis(level - 1, left, right, stringBuilder, list);
        //最后一个符号肯定是 ),不需要处理了
        if (level > 1) {
            StringBuilder stringLoop = new StringBuilder(stringBuilder);
            for (int i = left - right; i > 0; i--) {
                stringLoop.append(')');
                right++;
                generateParenthesis(level - 1, left, right, stringLoop, list);
            }
        }
    }
}
